Artikel zum Download
Dieser Artikel steht auch als PDF-Version zur Verfügung. Laden Sie ihn herunter, um ihn bequem offline zu lesen.
One-Time-Pad: Generierung in Anlehnung an Merkles Puzzle
Als „One-Time-Pad“ (OTP) wird das symmetrische Verschlüsselungsverfahren bezeichnet, bei welchem (dem Namen entsprechend) der Schlüssel nur einmal verwendet werden darf.
Es garantiert (unter bestimmten Voraussetzungen) die perfekte Sicherheit einer verschlüsselten Nachricht. Das bedeutet: Bei sachgemäßer Verwendung des Schlüssels kann die Nachricht nicht entschlüsselt werden.
Als Voraussetzungen für die Sicherheit bei der Verwendung des OTP gelten folgende Punkte:
· Der Schlüssel (das One-Time-Pad) darf nur für eine einzige Nachricht verwendet werden (Namensgeber).
· Die Generierung des Schlüssels muss mit einem kryptographisch sicherem Zufallszahlengenerator erfolgen.
· Die Länge des Schlüssels muss mindestens der Länge der Nachricht entsprechen.
· Der Schlüssel muss natürlich geheim gehalten werden.
Da es sich um eine symmetrische Verschlüsselung handelt, verwenden Sender und Empfänger der Nachricht den gleichen Schlüssel zum Codieren und Decodieren der Nachricht. Eine Herausforderung ist die Vereinbarung oder der Austausch des gemeinsamen Schlüssels.
Der Inhalt dieses Textes beschäftigt sich mit einer Methode zur Generierung des gemeinsamen Schlüssels. Einen Beispielcode werde ich dieser Beschreibung beifügen. Ich habe hierzu SQL gewählt, weil man so (auch ohne Überwachung der Software) die Möglichkeit hat, alle generierten Daten einzusehen und auch leicht nachvollziehen kann, wie sich mögliche Code- und/oder Strukturänderungen auf die Schlüsselfindung auswirken.
1. Matrix für den Schlüsselvergleich
Alice möchte Bob eine Nachricht zukommen lassen und informiert Bob (unverschlüsselt) über diese Absicht. Daraufhin generieren Alice und Bob (gemeinsam, aber jeder für sich) eine Matrix (Struktur und Daten) für den Schlüsselvergleich.
1.1.Infrastruktur
Die Infrastruktur bei Alice und Bob besteht (auf jeder Seite) jeweils aus den beiden Tabellen [OTP_MainData_Own] und [OTP_MainData_Ext].
Tabelle [OTP_MainData_Own]:
|
Spalte |
Bemerkung 1 |
Bemerkung 2 |
Typ |
|
[ID] |
Identity |
Tabellenschlüssel |
Ganzzahl |
|
[RI] |
RandomInformation |
Zufallszahl als Information |
Ganzzahl |
|
[RK] |
RandomKey |
Zufallszahl als Schlüssel |
Ganzzahl |
|
[RI_RK] |
Berechnete Spalte |
[RK]^[RI] (bitweiser Oder-Vergleich) |
Ganzzahl |
|
[HX_RI_RK] |
Berechnete Spalte |
Spalte [RI_RK] binär |
binär |
|
[HS_RI_RK] |
Berechnete Spalte |
Spalte [HX_RI_RK] als SHA-256-Hash |
binär |
Tabelle [OTP_MainData_Ext]:
|
Spalte |
Bemerkung 1 |
Bemerkung 2 |
Typ |
|
[ID] |
Identity |
Tabellenschlüssel |
Ganzzahl |
|
[RI] |
RandomInformation |
Zufallszahl als Information |
Ganzzahl |
|
[RkOwn] |
RandomKeyOwn |
Zufallszahl als eigener Schlüssel |
Ganzzahl |
|
[HS_RI_RkExt] |
HashRandomInfo |
Externer (empfangener) Hashwert |
binär |
|
[RI_RkOwn] |
Berechnete Spalte |
[RK]^[RI] (bitweiser Oder-Vergleich) |
Ganzzahl |
|
[HX_RI_RkOwn] |
Berechnete Spalte |
Spalte [RI_RK] binär |
binär |
|
[HS_RI_RkOwn] |
Berechnete Spalte |
Spalte [HX_RI_RK] als SHA-256-Hash |
binär |
Für den einfacheren Ablauf (und zur Demonstration) des Schlüsselaustausches ist eine weitere Infrastruktur auf einer Plattform mit gemeinsamen Schreib- Leserechten (Interlayer) sinnvoll, aber nicht unbedingt erforderlich. Hier befinden sich 4 Tabellen:
· AliceOutRnd –> Speicherung der von Alice generierten Zufallszahlen
· AliceOutHs –> Speicherung der Hashwerte
· BobOutRnd –> Speicherung der von Bob generierten Zufallszahlen
· BobOutHs –> Speicherung der Hashwerte
Tabelle [AliceOutRnd]/[BobOutRnd]:
|
Spalte |
Bemerkung 1 |
Bemerkung 2 |
Typ |
|
[ID] |
Identity |
Tabellenschlüssel |
Ganzzahl |
|
[RI] |
RandomInformation |
Zufallszahl als Information |
Ganzzahl |
Tabelle [AliceOutHs]/[BobOutHs]:
|
Spalte |
Bemerkung 1 |
Bemerkung 2 |
Typ |
|
[ID] |
Identity |
Tabellenschlüssel |
Ganzzahl |
|
[HS_RI_RK] |
HashRandomInfo |
Hashwert |
binär |
1.2.Ablauf
Zur Demonstration und Nachverfolgung der Vorgänge beträgt im Beispiel die Länge jedes einzelnen Schlüsselfragments ein Byte (8 Bit).
Step 1: Befüllen der Tabelle [OTP_MainData_Own]
Beide Teilnehmer generieren Daten und laden diese zeilenweise in die jeweils eigene Tabelle [OTP_MainData_Own]. Hierzu müssen die beiden Spalten RI und RK mit Zufallszahlen (bei der Länge von einem Byte mit Werten zwischen 0 und 255) gefüllt werden. Die anderen Spalten werden automatisch gefüllt. Wenn man pro Sequenz durchschnittlich einen Treffer bei der Generierung des Schlüssels haben möchte sollten 256 Zeilen gefüllt werden. Das ist aber keine Grundsätzliche Anforderung: Es können auch mehr oder weniger Zeilen generiert werden. Hier ein Beispiel für die ersten 10 Zeilen:
Step 2: Senden der Tabelle [OTP_MainData_Own]
Der Inhalt der Tabelle [OTP_MainData_Own] (eigentlich nur die beiden Spalten [ID] und [RI]) wird von jedem Teilnehmer auf eine Plattform mit gemeinsamen Schreib- Leserechten (Interlayer) übertragen oder direkt an den anderen Teilnehmer gesendet. Dabei wird von Alice an die Tabelle [AliceOutRnd] und von Bob an [BobOutRnd] gesendet.
Step 3: Befüllen der Tabelle [OTP_MainData_Ext]
Die eigene Tabelle [OTP_MainData_Ext] wird von jedem Teilnehmer mit dem Inhalt der empfangenen Daten (oder direkt vom Interlayer, dabei liest Bob von Tabelle [AliceOutRnd] und Alice von Tabelle [BobOutRnd]) geladen. Diese Daten kommen also von Extern. Aus Sicht von Alice wird:
· die Spalte [OTP_MainData_Ext].[ID] gefüllt von [OTP_MainData_Own].[ID]
· die Spalte [OTP_MainData_Ext].[RI] gefüllt von [BobOutRnd].[RI]
· die Spalte [OTP_MainData_Ext].[RkOwn] gefüllt von [OTP_MainData_Own].[RK]
Dazu werden die beiden Tabellen über die Spalte [ID] miteinander verknüpft.
Step 4: Senden der Tabelle [OTP_MainData_Ext]
Der Inhalt der Tabelle [OTP_MainData_Ext] (eigentlich nur der Inhalt der beiden Spalten [ID] und [HS_RI_RkOwn]) wird von jedem Teilnehmer (ähnlich wie Step 2) gesendet. Dabei wird von Alice an die Tabelle [AliceOutHs] und von Bob an [BobOutHs] gesendet.
Step 5: Aktualisieren der Tabelle [OTP_MainData_Ext]
Die Spalte [HS_RI_RkExt] der eigenen Tabelle [OTP_MainData_Ext] wird von jedem Teilnehmer aktualisiert. Dabei liest Bob von Spalte [AliceOutHs].[HS_RI_RK] und Alice von Spalte [BobOutHs].[HS_RI_RK].
Dazu werden die beiden Tabellen jeweils über die Spalte [ID] miteinander verknüpft.
Step 6: Auswertung
Sowohl Alice als auch Bob können die für eine Verschlüsselung gewonnenen Keys auf ihrer Seite einsehen. Dazu muss die Tabelle [OTP_MainData_Own] zusammen mit der Tabelle [OTP_MainData_Ext] ausgewertet werden. Eine einfache SQL-Abfrage der Tabellen sieht folgendermaßen aus:
SELECT [Own].[ID]
,[Own].[RI]
,[Own].[RK]
,[Own].[RI_RK]
,[Own].[HS_RI_RK]
FROM [dbo].[OTP_MainData_Own] [Own]
Inner Join [dbo].[OTP_MainData_Ext]
[Ext]
ON [Ext].[ID] = [Own].[ID]
And [Ext].[HS_RI_RkExt] = [Own].[HS_RI_RK]
Diese Abfrage liefert im Beispiel folgende Ergebnisse:
Es haben sich also in der Spalte [RK] (bei Alice und Bob) vier übereinstimmende und somit vier mögliche Schlüssel ergeben: 242, 25, 26, 84.
Segment, Sequenz, Session:
Falls es bisher Unklarheiten mit der hierarchischen Zuordnung gegeben haben sollte:
· Eine einzelne Zeile entspricht einem Segment.
· Eine Sequenz enthält genau die Anzahl an Zeilen, um mit einer Wahrscheinlichkeit von 1 ein Schlüsselfragment zu finden.
· Eine Session enthält alle Sequenzen, welche zur Vereinbarung des Gesamtschlüssels erforderlich sind.
2. Sicherheitsaspekte
Zufallszahlengenerator: Das Verschlüsselungsverfahren OTP ist so sicher, dass ein verschlüsselter Text ohne Kenntnis des Schlüssels NICHT entschlüsselt werden kann, es sei denn, es wurden Zufallszahlen verwendet, welche "nicht ausreichend zufällig" sind, etwa weil der Zufallszahlgenerator Schwächen aufweist oder nicht richtig bedient wird. Wie die Generierung der Zufallszahlen sicherer gemacht werden kann, ist nicht Bestandteil dieser Abhandlung. Im Beispiel wird die SQL-Funktion RAND() mit der Funktion NewID() als Ausgangswert verwendet.
Hash- Algorithmus: Bei dem hier dargestellten Verfahren ist die Generierung des Hash-Wertes von entscheidender Bedeutung. Im Beispiel wurde der SHA2-256– Algorithmus verwendet. Es könnten aber auch beliebige andere Hash-Algorithmen verwendet werden. Der Hashwert einer Zufallszahl wird im Verfahren gesendet und ist für andere sichtbar. Deshalb ist es wichtig, dass vom Hash-Wert nicht auf den Ausgangswert geschlossen werden kann. Falls der Wertebereich zu klein ist (so wie hier im vereinfachten Beispiel), kann der Angreifer natürlich auch eine Hash-Tabelle verwenden und einfach nachschauen, ohne den Wert jedesmal neu generieren zu müssen. Deshalb sollte unbedingt mit einem wechselnden Wertebereich (nicht Bestandteil dieser Abhandlung) gearbeitet werden.
Schlüsselzuordnung: Weil die Schlüsselfragmente einzeln angreifbar sind wäre es fast sträflich, wenn ohne weitere Maßnahmen eine 1:1 Zuordnung von Schlüsselfragment und Information erfolgen würde. Erst wenn in einer Session der komplette Schlüsselsatz (umfasst mehrere Sequenzen) gebildet wurde, darf daraus der neue (gesamte) Schlüssel, mit Abhängigkeiten zwischen allen Fragmenten gebildet werden.
Theoretische Sicherheit: Ein Angreifer, welcher die gesamte Kommunikation mitschneidet, ist theoretisch in der Lage ebenfalls einen passenden Schlüssel zu generieren. Wenn vereinbart wird, dass alle gefundenen Schlüssel zur Generierung des Gesamtschlüssels verwendet werden, müssen (bei der im Beispiel verwendeten Schlüssellänge von einem Byte) Alice und Bob im Durchschnitt 256 Zeichen verschlüsseln und vergleichen, um zwei Schlüsselfragmente zu erhalten.
Ein Angreifer müsste für die gleiche Anzahl 2 x 256 x 256/2 = 65.536 Zeichen verschlüsseln und vergleichen. Die ersten 5 (der 2 x 256 Zeilen) für ihn zugänglichen Zeilen könnten wie folgt aussehen:
Bei der Schlüsselfindung müssen die von Alice und Bob gelieferten Hashwerte getauscht werden. Die Suche für das 1. Schlüsselfragment (hier 242) lautet dann:
1.1.
Mit welchem
Schlüssel müsste ich den Wert 20 verschlüsseln um auf den Hashwert <<0x5CF0EB4CC11176A4A6DB30ECF970BB431C604D35045953872F33C9D2B7F64A84>> zu kommen?
Antwort: 242 Diese Antwort erhält man im Durchschnitt nach 256/2 = 128
Operationen.
1.2.
Mit welchem
Schlüssel müsste ich den Wert 224 verschlüsseln um auf den Hashwert <<0x5BC67471C189D78C76461DCAB6141A733BDAB3799D1D69E0C419119C92E82B3D>> zu kommen?
Antwort: 242 Diese Antwort erhält man im Durchschnitt nach 256/2 = 128
Operationen.
1.3. Sind diese beiden Werte gleich? Antwort: ja –> erstes Schlüsselfragment gefunden!
Die Suche nach dem 2. Schlüsselfragment:
2.1.
Mit welchem
Schlüssel müsste ich den Wert 169 verschlüsseln um auf den Hashwert <<0x9E9F4657C20E9D6C5CF79245D4E36EE6AC9F6DCAFFC3DE76CA2DD51AACD3EC3A>> zu kommen?
Antwort: 238. Diese Antwort erhält man im Durchschnitt nach 256/2 = 128
Operationen.
2.2.
Mit welchem
Schlüssel müsste ich den Wert 205 verschlüsseln um auf den Hashwert
<<0x0764C726A72F8E1D245F332A1D022FFFDADA0C4CB2A016886E4B33B66CB9A53F>> zu kommen?
Antwort: 240. Diese Antwort erhält man im Durchschnitt nach 256/2 = 128
Operationen.
2.3. Sind diese beiden Werte gleich Antwort: nein –> kein Schlüsselfragment!
Es sind also 2 x 128 x 256 = 65.536 Operationen notwendig, um die ersten Schlüsselfragmente zu finden. Für Alice und Bob sind es jeweils 256 Operationen. Ein Angreifer muss also (wenn die gesamte Kommunikation belauscht und mitgeschnitten wurde) die quadratische Anzahl an Operationen ausführen um den Schlüssel nachzubauen. Auch für die im ‚Merkles Puzzle‚ beschriebene originale Vorgehensweise konnte diese (für moderne Verschlüsselungsverfahren als zu gering befundene) Sicherheit nicht verbessert werden.
Ich habe mal mit meinem Rechner (5 Jahre alt) einen Test mit einem Schlüsselfragment mit einer Länge von 2 Byte gefahren: 65.536 Operationen dauerten eine Sekunde. Falls die Dauer für eine Operation bei Alice, Bob und dem Angreifer vergleichbar sind, würde der Angreifer hierfür 18 Stunden benötigen. Bei einer Länge von 3 Byte hat mein Rechner 290 Sekunden (ca. 5 Minuten) benötigt. Das bedeutet für den Angreifer mit gleicher Leistung umgerechnet 154 Jahre.
Und leider existiert noch Abkürzung für die Schritte 2 und 3. Statt der in 1.2. und 1.3 beschrieben Vorgehensweise könnte der Angreifer auch einfach folgende Überlegung anstellen:
·
Liefert eine
Verschlüsselung des Wertes 224 mit dem Schlüssel 242 (Key 1) den
Hashwert
<<0x5BC67471C189D78C76461DCAB6141A733BDAB3799D1D69E0C419119C92E82B3D>>?
Antwort: ja –> Schlüsselfragment gefunden! Für diese Antwort ist nur
eine Operation erforderlich.
Und die Schritte 2.3 / 3.3 würden sich wie folgt verkürzen:
Liefert
eine Verschlüsselung des Wertes 205 mit dem Schlüssel 238 (Key 1)
den Hashwert
<<0x0764C726A72F8E1D245F332A1D022FFFDADA0C4CB2A016886E4B33B66CB9A53F>>?
Antwort: nein –> kein Schlüsselfragment! Für diese Antwort ist
wieder nur eine Operation erforderlich
Aktuell ist der von mir verwendete Code für eine praktische Anwendung noch zu langsam, wenn eine Sequenz mit 224 Operationen schon 5 Minuten benötigt, um ein einziges Schlüsselfragment von 3 Byte zu finden. Eine Fragmentlänge von 2 Byte ist aber nicht sicher genug, weil es bereits nach 18 Stunden nachgebaut werden kann. Natürlich kann man mehrere Fragmente zu einem großen Schlüssel zusammenfügen. Wenn man aber auf die dargestellt quadratische Sicherheit nicht verzichten möchte (obwohl dieser Exponent NICHTS über die tatsächliche Sicherheit aussagt) ist die Kombination mehrerer Schlüssel zu einen Gesamtschlüssel keine gute Idee.
Beispiel: Angenommen, Alice und Bob führen jeder 1020 Operationen aus. Dann müsste ein Angreifer 1040 Operationen ausführen, um den Schlüssel mit den abgefangenen Informationen nachzubauen. Wenn jetzt jedoch der Gesamtschlüssel aus zwei von diesen Schlüsselfragmenten besteht (2 x 1020 Operationen) müsste der Angreifer 2 x 1040 Operationen ausführen. Das Quadrat von 2 x 1020 ist aber 4 x 1040 und somit größer als 2 x 1040. Die quadratische Sicherheit wird durch die Kombination mehrerer Schlüssel also nicht mehr erreicht. Laut vorhandener Literatur lässt sich diese quadratische Sicherheit nicht verbessern, außer vielleicht mit einem Trick…
3. Die Pyramide
Die Methode der Pyramide kann man bei vielen Gelegenheiten anwenden: Zum Beispiel beim Entwurf eines Gebäudes. Angenommen, es soll eine Grundfläche von 400 m² haben und 30 Stockwerke besitzen, von denen jedes (bei gleichmäßiger Lastverteilung) die Gründung mit 10 kN/m² belasten würde. Aber dann kommt ein Baugrundgutachten, welches 200 kN/m² als maximal zulässigen Bodendruck ausweist. 30 Stockwerke x 10 kN/m² = 300 kN/m² –> geht also nicht.
Mit dem Pyramidentrick kommt man aber weiter: Man baut (in der 1. Stufe) einfach nur bis zur Hälfte der zulässigen Last: Das wären also 10 Stockwerke. Ab dem 11. Stockwerk (in der 2. Stufe) reduziert man die Gebäudefläche auf die Hälfte. (das wären dann 200 m²) und baut weitere 20 Stockwerke oben drauf.
10 Stockwerke x 10 kN/m² x 400 m² = 40.000 kN
+ 20 Stockwerke x 10 kN/m² x 200 m² = 40.000 kN
———————————————–
= 30 Stockwerke = 80.000 kN
===============================================
80.000 kN / 400 m² = 200 kN/m² –> geht also doch.
Theoretisch könnte man noch höher bauen, wenn man in der 2. Stufe statt der ursprünglichen 20 wieder nur 10 Geschosse baut, dafür aber eine 3. Stufe einplant, welche (natürlich wieder nur mit der halben Geschossfläche von 100 m²) die restlichen 20 Geschosse bekommt
10 Stockwerke x 10 kN/m² x 400 m² = 40.000 kN
+ 10 Stockwerke x 10 kN/m² x 200 m² = 20.000 kN
+ 20 Stockwerke x 10 kN/m² x 100 m² = 20.000 kN
———————————————–
= 40 Stockwerke = 80.000 kN
===============================================
Die 80.000 kN wurden wieder nicht überschritten. Das könnte man (wenn andere Gebäudeparameter dadurch nicht beeinträchtigt werden) immer weiter so fortsetzen.
Die (eigentlich nicht zu verbessernde) quadratische Sicherheit der hier vorgestellten Methode zur Generierung eines gemeinsamen Schlüssels kann man nur deshalb vergrößern, weil es sich nicht um eine Kopie des "Merkles Puzzle" handelt, sondern diesem nur ähnlich ist. Ehrlich gesagt habe ich auch erst von der Existenz des "Merkles Puzzle" erfahren, als mein Code bereits funktionierte und Ergebnisse lieferte. Hier sind die Unterschiede:
|
|
Merkles Puzzle |
Schlüsselaustausch-Matrix |
|
Schlüsselfindung |
Getrennt: Alice stellt Bob viele Aufgaben (Chiffrate) und Bob versucht eine dieser Aufgabe zu lösen (zu entschlüsseln). Er informiert Alice über die gelöste Aufgabe. Somit gilt der Schlüssel als vereinbart. |
Gemeinsam: Alice und Bob füllen jeder in einer Tabelle 2 Spalten mit Zufallszahlen: Eine zufällige Information und einen zufälligen Schlüssel. In jeder Zeile wird die Information mit dem Schlüssel chiffriert und als Hashwert an den anderen Teilnehmer verschickt. |
|
Schlüsselanzahl |
Einzeln: Bei jeder (durch Bob) gelösten Aufgabe gilt ein gemeinsamer Schlüssel als vereinbart. |
Als Sequenz: Es kann sein, dass in einer Sequenz mehrere oder auch keine Schlüsselfragmente gefunden werden. Beide Partner wissen am Ende jeder Sequenz sofort, wieviele Schlüsselfragmente gefunden wurden. |
|
Verschlüsselungs-verfahren |
Beliebige symmetrische Verschlüsselungsverfahren |
Die Schlüsselaustausch-Matrix wurde speziell für das One-Time-Pad und symmetrische Verschlüsselung entwickelt. |
Bei der Generierung des gemeinsamen Schlüssels mit Hilfe der Schlüsselaustauschmatrix ist es möglich die Methode der Pyramide anzuwenden, um die Beschränkung der quadratischen Sicherheit zu durchbrechen, so, wie bei dem Gebäude die Höhenbeschränkung durchbrochen wurde. Wenn z.B. der Standard-Werteraum nicht 256 Zahlen (0 bis 255) umfasst, sondern nur 10 Werte, lässt es sich deutlicher erklären. Bei 10 möglichen Werten (zwischen 0 und 9) müsste die Sequenz auch 10 Segmente umfassen. Stattdessen verwendet man aber nur in den ersten 9 Zeilen (Bereich 1) die Werte von 0 bis 9, und die 10. Zeile wird aufgesplittet in weitere 10 Zeilen zwischen 0 99 (Bereich 2).
Hier ein Beispiel mit generierten Schlüsseln:
|
Bereich 1 |
|
Bereich 2 |
||||||
|
Zeile |
Alice |
Bob |
Key gefunden? |
Zeile |
Alice |
Bob |
Key gefunden? |
|
|
1.1 |
3 |
5 |
Nein |
2.1 |
63 |
56 |
Nein |
|
|
1.2 |
3 |
3 |
Ja |
2.2 |
44 |
63 |
Nein |
|
|
1.3 |
6 |
5 |
Nein |
2.3 |
24 |
20 |
Nein |
|
|
1.4 |
2 |
6 |
Nein |
2.4 |
40 |
87 |
Nein |
|
|
1.5 |
4 |
3 |
Nein |
2.5 |
33 |
9 |
Nein |
|
|
1.6 |
5 |
5 |
Ja |
2.6 |
49 |
12 |
Nein |
|
|
1.7 |
10 |
7 |
Nein |
2.7 |
23 |
25 |
Nein |
|
|
1.8 |
6 |
8 |
Nein |
2.8 |
46 |
46 |
Ja |
|
|
1.9 |
9 |
10 |
Nein |
2.9 |
89 |
31 |
Nein |
|
|
2.10 |
78 |
65 |
Nein |
|||||
Die Gesamtwahrscheinlichkeit (um in dieser Sequenz ein Schlüsselfragment zu finden) liegt weiterhin bei 1,0. Allerdings hat sich der Sicherheitsexponent erhöht. Er liegt jetzt bei 2,375 (siehe Stufe 2 der folgenden Übersichtstabelle):
|
Stufen |
Zeilen |
Werte |
Versuche des Angreifers |
Sicherheit (Exponent) |
|
1 |
10 |
10 |
100 |
|
|
Summe: |
10 |
10 |
100 |
2 |
|
1 |
9 |
10 |
90 |
|
|
2 |
10 |
100 |
1.000 |
|
|
Summe: |
19 |
|
1.090 |
2,3753024 |
|
1 |
9 |
10 |
90 |
|
|
2 |
9 |
100 |
900 |
|
|
3 |
10 |
1.000 |
10.000 |
|
|
Summe: |
28 |
|
10.990 |
2,792367941 |
|
1 |
9 |
10 |
90 |
|
|
2 |
9 |
100 |
900 |
|
|
3 |
9 |
1.000 |
9.000 |
|
|
4 |
10 |
10.000 |
100.000 |
|
|
Summe: |
37 |
|
109.990 |
3,214735148 |
|
1 |
9 |
10 |
90 |
|
|
2 |
9 |
100 |
900 |
|
|
3 |
9 |
1.000 |
9.000 |
|
|
4 |
9 |
10.000 |
90.000 |
|
|
5 |
10 |
100.000 |
1.000.000 |
|
|
Summe: |
46 |
|
1.099.990 |
3,633354552 |
|
1 |
9 |
10 |
90 |
|
|
2 |
9 |
100 |
900 |
|
|
3 |
9 |
1.000 |
9.000 |
|
|
4 |
9 |
10.000 |
90.000 |
|
|
5 |
9 |
100.000 |
900.000 |
|
|
6 |
10 |
1.000.000 |
10.000.000 |
|
|
Summe: |
55 |
|
10.999.990 |
4,045933835 |
Wie man sehen kann, lässt sich das so immer weiter fortführen. Interessant wird es aber, wenn nicht 10 Zeilen als Basis genommen werden, sondern nur 2 Zeilen:
|
Stufen |
Zeilen |
mögliche Werte |
Versuche des Angreifers |
Sicherheit (Exponent) |
|
1 |
1 |
2 |
2 |
1,0000 |
|
2 |
1 |
4 |
4 |
1,6309 |
|
3 |
1 |
8 |
8 |
1,9037 |
|
4 |
1 |
16 |
16 |
2,1133 |
|
5 |
1 |
32 |
32 |
2,3034 |
|
6 |
1 |
64 |
64 |
2,4854 |
|
7 |
1 |
128 |
128 |
2,6629 |
|
8 |
1 |
256 |
256 |
2,8374 |
|
9 |
1 |
512 |
512 |
3,0095 |
|
10 |
1 |
1.024 |
1.024 |
3,1793 |
|
11 |
1 |
2.048 |
2.048 |
3,3471 |
|
12 |
1 |
4.096 |
4.096 |
3,5130 |
|
13 |
1 |
8.192 |
8.192 |
3,6770 |
|
14 |
1 |
16.384 |
16.384 |
3,8393 |
|
15 |
1 |
32.768 |
32.768 |
4,0000 |
|
16 |
1 |
65.536 |
65.536 |
4,1591 |
|
17 |
1 |
131.072 |
131.072 |
4,3166 |
|
18 |
1 |
262.144 |
262.144 |
4,4728 |
|
19 |
1 |
524.288 |
524.288 |
4,6276 |
|
20 |
1 |
1.048.576 |
1.048.576 |
4,7811 |
|
21 |
1 |
2.097.152 |
2.097.152 |
4,9334 |
|
22 |
1 |
4.194.304 |
4.194.304 |
5,0845 |
|
23 |
1 |
8.388.608 |
8.388.608 |
5,2345 |
|
24 |
1 |
16.777.216 |
16.777.216 |
5,3835 |
|
25 |
1 |
33.554.432 |
33.554.432 |
5,5314 |
|
26 |
1 |
67.108.864 |
67.108.864 |
5,6784 |
|
27 |
1 |
134.217.728 |
134.217.728 |
5,8244 |
|
28 |
1 |
268.435.456 |
268.435.456 |
5,9696 |
|
29 |
1 |
536.870.912 |
536.870.912 |
6,1139 |
|
30 |
1 |
1.073.741.824 |
1.073.741.824 |
6,2573 |
|
31 |
1 |
2.147.483.648 |
2.147.483.648 |
6,4000 |
|
32 |
1 |
4.294.967.296 |
4.294.967.296 |
6,5419 |
|
33 |
1 |
8.589.934.592 |
8.589.934.592 |
6,6831 |
|
34 |
1 |
17.179.869.184 |
17.179.869.184 |
6,8236 |
|
35 |
1 |
34.359.738.368 |
34.359.738.368 |
6,9634 |
|
36 |
1 |
68.719.476.736 |
68.719.476.736 |
7,1025 |
|
37 |
1 |
137.438.953.472 |
137.438.953.472 |
7,2410 |
|
38 |
1 |
274.877.906.944 |
274.877.906.944 |
7,3788 |
|
39 |
1 |
549.755.813.888 |
549.755.813.888 |
7,5161 |
|
40 |
1 |
1.099.511.627.776 |
1.099.511.627.776 |
7,6527 |
|
41 |
1 |
2.199.023.255.552 |
2.199.023.255.552 |
7,7889 |
|
42 |
1 |
4.398.046.511.104 |
4.398.046.511.104 |
7,9244 |
|
43 |
1 |
8.796.093.022.208 |
8.796.093.022.208 |
8,0594 |
|
44 |
1 |
17.592.186.044.416 |
17.592.186.044.416 |
8,1940 |
|
45 |
1 |
35.184.372.088.832 |
35.184.372.088.832 |
8,3280 |
|
46 |
1 |
70.368.744.177.664 |
70.368.744.177.664 |
8,4615 |
|
47 |
1 |
140.737.488.355.328 |
140.737.488.355.328 |
8,5945 |
|
48 |
2 |
281.474.976.710.656 |
562.949.953.421.312 |
8,8313 |
|
Summe |
49 |
— |
844.424.930.131.966 |
8,8313 |
Wie man sieht, kann so der Sicherheitsexponent leicht auf einen hohen Wert gebracht werden. Es ist nur ärgerlich, dass der Exponent eigentlich NICHTS über die tatsächliche Sicherheit aussagt. Auch ist die Wahrscheinlichkeit, dass in einer Sequenz überhaupt ein Fragment gefunden wird weiterhin bei 1. In welchem Segment sich das Fragment befindet, wird aber vom (gewichteten) Zufall bestimmt.
Die Schlüsselaustauschpartner können die oben genannten Erkenntnisse nutzen, um (im Rahmen ihrer Möglichkeiten) den Schlüsselaustausch sicherer zu gestalten.
4. Nutzung der Pyramide
Grundlage zur Vereinbarung der Parameter für die Schlüsselgenerierung sollte sein:
a) Die Länge der zu verschlüsselnden Nachricht
b) Die angestrebte Mindestsicherheit, welche natürlich vom Nachrichteninhalt abhängig ist, und vom Sender eingeschätzt werden muss.
c) Die Leistungsfähigkeit der Systeme, auf welchen die Schlüsselgenerierung erfolgen soll.
Wobei die Punkte a) und b) jeweils als Mindestanforderungen zu verstehen sind und Punkt c) als Obergrenze des Sinnvollen und Machbaren.
Angenommen, man einigt sich bei der Schlüsselvereinbarung auf die Verwendung einer Pyramide, zum Beispiel auf das oben dargestellte Model (mit der 2 als Basis) auf 24 Stufen, hat das folgende Konsequenzen:
· In dieser Stufe gibt es 16.777.216 möglich Werte. Also ist die Wahrscheinlichkeit, dass auf dieser Stufe ein Schlüsselfragment vereinbart wird 1/16.777.216 (0,0000000596). Es müssten also insgesamt 16.777.216 Sequenzen ausgetauscht werden, damit in der kompletten Session mindestens 1 Fragment mit diesem Sicherheitsanspruch enthalten ist. Falls kein Fragment in diesem Bereich gefunden wird (dies aber als Mindestsicherheit vereinbart wurde), müsste die komplette Session verworfen werden.
·
Ein Angreifer müsste
(wenn er keine Abkürzung nimmt) 8,44 x 1014 Operationen
ausführen:
((224 + 225 – 2) x 16.777.216 = 844.424.896.577.536), um
den Schlüssel aus den mitgeschnittenen Informationen zu konstruieren.
· Mit einer Session von 16.777.216 Fragmenten könnte man bequem (auch wenn man für jedes Byte der Nachricht durchschnittlich 8 Sequenzen durchführen möchte) eine Nachricht mit einer Länge von 2 MB verschlüsseln.
· Wenn man für alle Parteien eine Rate von ca. 225 Operationen/Sekunde annimmt, benötigen die Partner 25 Sekunden für die Schlüsselvereinbarung, ein Angreifer jedoch 19,4 Monate, um den Schlüssel zu rekonstruieren. Hierbei wurde jedoch die Zeitdauer zur Bildung der Zufallszahlen gegenüber der Zeitdauer zur Generierung eines Hashwertes vernachlässigt (der Angreifer muss keine Zufallszahlen generieren). Es sollte also ein (im Vergleich zum Zufallsgenerator) relativ aufwändiger Hashalgorithmus eingesetzt werden: Der Angreifer muss nämlich zwingend den gleichen Algorithmus verwenden.
Auf Stufe 25 würde sich die Zeitdauer für die Partner verdoppeln, für den Angreifer jedoch vervierfachen. Wenn sich die Rechengeschwindigkeit global erhöht, erfolgt dies zugunsten der Partner, nicht zugunsten der Angreifer. Angenommen, alle Parteien können mit einer Rate von 30 Operationen/Sekunde rechnen, würden die Partner die Stufe 30 als Mindestsicherheit vereinbaren und zu Generierung des Schlüssels ca. 30 Sekunden benötigen, ein Angreifer würde hingegen für die Rekonstruktion des Schlüssels ca. 100 Jahre benötigen.
Steinbach-Hallenberg, 08/2019 – 01/2024
Stefan Ulbrich